<html>
 <head>
  <meta charset="UTF-8">
 </head>
 <body>
  <h1 data-lake-id="uHtJN" id="uHtJN"><span data-lake-id="u85c35f90" id="u85c35f90">典型回答</span></h1>
  <p data-lake-id="u247404d6" id="u247404d6"><br></p>
  <p data-lake-id="u2d71457c" id="u2d71457c"><span data-lake-id="udcf9ba49" id="udcf9ba49">ForkJoinPool和ExecutorService都是Java中常用的线程池的实现，他们主要在实现方式上有一定的区别，所以也就会同时带来的适用场景上面的区别。</span></p>
  <p data-lake-id="u5eaa9943" id="u5eaa9943"><span data-lake-id="ua0928edf" id="ua0928edf">​</span><br></p>
  <p data-lake-id="ud9ddecc4" id="ud9ddecc4"><span data-lake-id="u5da20a0e" id="u5da20a0e">首先在</span><strong><u><span data-lake-id="u05c18bd4" id="u05c18bd4">实现方式</span></u></strong><span data-lake-id="ud31048d5" id="ud31048d5">上，</span><strong><span data-lake-id="u24fbd69f" id="u24fbd69f">ForkJoinPool 是基于工作窃取（Work-Stealing）算法实现的线程池</span></strong><span data-lake-id="u9d5ca1d9" id="u9d5ca1d9">，ForkJoinPool 中每个线程都有自己的工作队列，用于存储待执行的任务。当一个线程执行完自己的任务之后，会从其他线程的工作队列中窃取任务执行，以此来实现任务的动态均衡和线程的利用率最大化。</span></p>
  <p data-lake-id="ua49dbb97" id="ua49dbb97"><span data-lake-id="u4356855d" id="u4356855d">​</span><br></p>
  <p data-lake-id="uf72e8c2e" id="uf72e8c2e"><strong><span data-lake-id="u1dc0fe9c" id="u1dc0fe9c">ThreadPoolExecutor 是基于任务分配（Task-Assignment）算法实现的线程池</span></strong><span data-lake-id="uf2cc22be" id="uf2cc22be">，ThreadPoolExecutor 中线程池中有一个共享的工作队列，所有任务都将提交到这个队列中。线程池中的线程会从队列中获取任务执行，如果队列为空，则线程会等待，直到队列中有任务为止。</span></p>
  <p data-lake-id="ud76a3620" id="ud76a3620"><span data-lake-id="u50978f56" id="u50978f56">​</span><br></p>
  <p data-lake-id="u26deecc1" id="u26deecc1"><span data-lake-id="u98dd463f" id="u98dd463f">ForkJoinPool 中的任务通常是一些可以分割成多个子任务的任务，例如快速排序。每个任务都可以分成两个或多个子任务，然后由不同的线程来执行这些子任务。在这个过程中，ForkJoinPool 会自动管理任务的执行、分割和合并，从而实现任务的动态分配和最优化执行。</span></p>
  <p data-lake-id="ub3032886" id="ub3032886"><span data-lake-id="u0c01b007" id="u0c01b007">​</span><br></p>
  <p data-lake-id="uc277c867" id="uc277c867" style="text-align: center"><img src="https://cdn.nlark.com/yuque/0/2023/png/5378072/1703309008970-55dbd865-15ab-4e24-bf11-1babe97ad112.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_52%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="u9a1e13a3" id="u9a1e13a3"><span data-lake-id="ue909ae0c" id="ue909ae0c">​</span><br></p>
  <p data-lake-id="uf3062af9" id="uf3062af9"><span data-lake-id="ube94c82a" id="ube94c82a">ForkJoinPool 中的工作线程是一种特殊的线程，与普通线程池中的工作线程有所不同。它们会自动地创建和销毁，以及自动地管理线程的数量和调度。这种方式可以降低线程池的管理成本，提高线程的利用率和并行度。</span></p>
  <p data-lake-id="u955fe4f6" id="u955fe4f6"><span data-lake-id="ua1482aa2" id="ua1482aa2">​</span><br></p>
  <p data-lake-id="u9c45bfd0" id="u9c45bfd0"><span data-lake-id="ue55fd2c5" id="ue55fd2c5">ThreadPoolExecutor 中线程的创建和销毁是静态的，线程池创建后会预先创建一定数量的线程，根据任务的数量动态调整线程的利用率，不会销毁线程。如果线程长时间处于空闲状态，可能会占用过多的资源。</span></p>
  <p data-lake-id="ud3bdf5f2" id="ud3bdf5f2"><br></p>
  <p data-lake-id="u7a0fbd65" id="u7a0fbd65"><span data-lake-id="u47660ea2" id="u47660ea2">在</span><strong><u><span data-lake-id="u4d891cc9" id="u4d891cc9">使用场景</span></u></strong><span data-lake-id="u48dd0d9a" id="u48dd0d9a">上也有区别，ExecutorService 适用于处理较小的、相对独立的任务，任务之间存在一定的依赖关系。例如，处理网络请求、读取文件、执行数据库操作等任务。</span></p>
  <p data-lake-id="u8acf9364" id="u8acf9364"><span data-lake-id="uf7bf4029" id="uf7bf4029">​</span><br></p>
  <p data-lake-id="uaa623641" id="uaa623641"><span data-lake-id="ub21b68a6" id="ub21b68a6">ForkJoinPool 适用于于以下场景：</span></p>
  <p data-lake-id="uec984c5d" id="uec984c5d"><span data-lake-id="uc4242ac7" id="uc4242ac7">​</span><br></p>
  <ol list="ua73af5cc">
   <li fid="uf348b327" data-lake-id="uf029f69d" id="uf029f69d" data-lake-index-type="true"><strong><span data-lake-id="u7b7f56db" id="u7b7f56db">大任务分解为小任务</span></strong><span data-lake-id="ua668724f" id="ua668724f">：适用于可以递归分解为更小任务的大型任务。ForkJoinPool 通过分而治之的方式，将大任务拆分为小任务，这些小任务可以并行处理。</span></li>
   <li fid="uf348b327" data-lake-id="u9c29f103" id="u9c29f103" data-lake-index-type="true"><strong><span data-lake-id="u66639886" id="u66639886">计算密集型任务</span></strong><span data-lake-id="udb36748a" id="udb36748a">：对于需要大量计算且能够并行化的任务，ForkJoinPool 是一个理想的选择。它能够有效利用多核处理器的优势来加速处理过程。</span></li>
   <li fid="uf348b327" data-lake-id="u81552083" id="u81552083" data-lake-index-type="true"><strong><span data-lake-id="u2ed806c5" id="u2ed806c5">异构任务并行处理</span></strong><span data-lake-id="u362dfd07" id="u362dfd07">：当任务之间没有或很少有依赖性时，ForkJoinPool 可以帮助并行执行这些任务，从而提高效率。</span></li>
   <li fid="uf348b327" data-lake-id="u93152a5e" id="u93152a5e" data-lake-index-type="true"><strong><span data-lake-id="u6df8080b" id="u6df8080b">递归算法的并行化</span></strong><span data-lake-id="u3771d642" id="u3771d642">：适合于可以用递归方法解决的问题，如快速排序、归并排序、图像处理中的分区算法等。</span></li>
   <li fid="uf348b327" data-lake-id="u1a809cd5" id="u1a809cd5" data-lake-index-type="true"><strong><span data-lake-id="u95cc6b29" id="u95cc6b29">数据聚合任务</span></strong><span data-lake-id="ue14e9b3c" id="ue14e9b3c">：在处理需要聚合多个数据源结果的任务时（例如，遍历树结构并聚合结果），ForkJoinPool 提供了有效的方式来并行化这一过程。</span></li>
  </ol>
  <p data-lake-id="u33176c72" id="u33176c72"><span data-lake-id="u2e05c444" id="u2e05c444">​</span><br></p>
  <blockquote data-lake-id="uab5b8b59" id="uab5b8b59">
   <p data-lake-id="ub49289fa" id="ub49289fa"><span data-lake-id="u2dda96d6" id="u2dda96d6">递归方法通常涉及到一定程度的依赖性，那么上面的第三、第四点不冲突吗？</span></p>
   <p data-lake-id="u11aa1a03" id="u11aa1a03"><span data-lake-id="ud8a7c73d" id="ud8a7c73d">​</span><br></p>
   <p data-lake-id="uc3dc2301" id="uc3dc2301"><span data-lake-id="u1c682fa9" id="u1c682fa9">异构任务并行处理指的是那些彼此独立的任务，它们可以同时执行而互不干扰。在这种情况下，ForkJoinPool 很适合执行多个不相关的任务，特别是当这些任务没有数据依赖或顺序要求时。</span></p>
   <p data-lake-id="u146d024a" id="u146d024a"><span data-lake-id="uc74d68d5" id="uc74d68d5">​</span><br></p>
   <p data-lake-id="u75190371" id="u75190371"><span data-lake-id="u697f97f1" id="u697f97f1">尽管递归算法中的每一步通常都依赖于前一步的结果，但ForkJoinPool 的优势在于能够处理那些可以被分解成多个较小、独立子任务的递归问题。例如，在快速排序中，一旦数组被分割，每个子数组的排序可以独立进行。在这里，虽然总体上存在步骤依赖，但分解后的子任务可以并行执行。</span></p>
   <p data-lake-id="u0d3dca81" id="u0d3dca81"><span data-lake-id="u939558ae" id="u939558ae">​</span><br></p>
   <p data-lake-id="u8707c623" id="u8707c623"><span data-lake-id="u0afdba4e" id="u0afdba4e">所以，关键在于任务的可分解性和子任务之间的独立性。对于可分解为多个独立子任务的递归问题，ForkJoinPool 是一个强大的工具。而对于那些各个步骤紧密相连、不能有效分解的任务，ForkJoinPool 可能不是最佳选择。</span></p>
  </blockquote>
  <p data-lake-id="u8d354264" id="u8d354264"><br></p>
  <h1 data-lake-id="jZMun" id="jZMun"><span data-lake-id="u76313ec5" id="u76313ec5">扩展知识</span></h1>
  <p data-lake-id="u587d80e4" id="u587d80e4"><br></p>
  <h2 data-lake-id="ITUxb" id="ITUxb"><span data-lake-id="u7643da2d" id="u7643da2d">为什么CompletableFuture使用ForkJoinPool</span></h2>
  <p data-lake-id="u4a5fabd6" id="u4a5fabd6"><br></p>
  <p data-lake-id="ufdd7f535" id="ufdd7f535"><span data-lake-id="u65bfa520" id="u65bfa520">CompletableFuture 使用 ForkJoinPool 而不是 ExecutorService 的原因主要是因为它的执行模型和任务分割方式与 ForkJoinPool 更加匹配。</span></p>
  <p data-lake-id="u972fd4a5" id="u972fd4a5"><span data-lake-id="u664d5ab2" id="u664d5ab2">​</span><br></p>
  <p data-lake-id="u5d5ea7fe" id="u5d5ea7fe"><span data-lake-id="u6c456f81" id="u6c456f81">在 CompletableFuture 中，一个任务可以分割成多个子任务，并且这些子任务之间可以存在依赖关系。而</span><strong><span data-lake-id="u22c1ebc4" id="u22c1ebc4">ForkJoinPool 本身就是一种支持任务分割和合并的线程池实现，能够自动地处理任务的拆分和合并</span></strong><span data-lake-id="u5bc575e0" id="u5bc575e0">。而且，</span><strong><span data-lake-id="u43aa97df" id="u43aa97df">ForkJoinPool 还有一种工作窃取算法，能够自动地调整线程的负载，提高线程的利用率和并行度。</span></strong></p>
  <p data-lake-id="u8526e0a9" id="u8526e0a9"><span data-lake-id="ue69bca61" id="ue69bca61">​</span><br></p>
  <p data-lake-id="ua4afcfa0" id="ua4afcfa0"><strong><span data-lake-id="u47babda5" id="u47babda5">ForkJoinPool 还有一个特点，就是它的线程池大小是动态调整的。</span></strong><span data-lake-id="ub594c3c2" id="ub594c3c2">当任务比较少时，线程池的大小会自动缩小，从而减少了线程的数量和占用的系统资源。当任务比较多时，线程池的大小会自动增加，从而保证任务能够及时地得到执行。</span></p>
  <p data-lake-id="udffa35bf" id="udffa35bf"><span data-lake-id="ua840ffc8" id="ua840ffc8">​</span><br></p>
  <p data-lake-id="ube0a6e0e" id="ube0a6e0e"><span data-lake-id="u971ca79a" id="u971ca79a">如果使用 ExecutorService 来执行这些任务，需要手动地创建线程池、任务队列和任务执行策略，并且需要手动地处理任务的拆分和合并，实现起来相对比较复杂。</span></p>
  <p data-lake-id="ub37318c6" id="ub37318c6"><br></p>
  <p data-lake-id="ue90bf8f8" id="ue90bf8f8"><span data-lake-id="u79c17f4f" id="u79c17f4f">因此，ForkJoinPool 更加适合 CompletableFuture 的执行模型。</span></p>
  <p data-lake-id="u9a04ef87" id="u9a04ef87"><span data-lake-id="u98e05952" id="u98e05952">​</span><br></p>
  <h2 data-lake-id="jwepk" id="jwepk"><span data-lake-id="u2f51c7d2" id="u2f51c7d2">ForkJoinPool使用示例</span></h2>
  <p data-lake-id="uee0011be" id="uee0011be"><br></p>
  <p data-lake-id="u1bfde8f4" id="u1bfde8f4"><strong><span data-lake-id="u6fba5a31" id="u6fba5a31" class="lake-fontsize-12" style="color: var(--tw-prose-code)">ForkJoinPool</span></strong><span data-lake-id="u177bcc1b" id="u177bcc1b" class="lake-fontsize-12" style="color: rgb(55, 65, 81)"> 很适合用于快速排序（Quicksort）算法这种递归操作并行化，原因如下：</span></p>
  <p data-lake-id="ub87ba583" id="ub87ba583"><span data-lake-id="uf9b87a86" id="uf9b87a86" class="lake-fontsize-12" style="color: rgb(55, 65, 81)">​</span><br></p>
  <ol list="u7a39b028">
   <li fid="ud2193873" data-lake-id="ubce985f2" id="ubce985f2"><strong><span data-lake-id="u34e7e8d8" id="u34e7e8d8" class="lake-fontsize-12" style="color: var(--tw-prose-bold)">可分解性</span></strong><span data-lake-id="u37687617" id="u37687617" class="lake-fontsize-12" style="color: rgb(55, 65, 81)">：快速排序算法通过选取一个枢纽（pivot）元素将数组分割成两个子数组，一个包含小于枢纽的元素，另一个包含大于枢纽的元素。这种分割过程天然适合并行处理，因为一旦数组被分割，这两个子数组的排序可以独立进行。</span></li>
   <li fid="ud2193873" data-lake-id="ub0a2eb71" id="ub0a2eb71"><strong><span data-lake-id="u77ce9689" id="u77ce9689" class="lake-fontsize-12" style="color: var(--tw-prose-bold)">并行优势</span></strong><span data-lake-id="u6a6d055a" id="u6a6d055a" class="lake-fontsize-12" style="color: rgb(55, 65, 81)">：在大数据集上进行快速排序时，</span><strong><span data-lake-id="u769fc720" id="u769fc720" class="lake-fontsize-12" style="color: var(--tw-prose-code)">ForkJoinPool</span></strong><span data-lake-id="ud1604acc" id="ud1604acc" class="lake-fontsize-12" style="color: rgb(55, 65, 81)"> 可以显著减少排序所需的时间。通过将大数组分割成更小的部分并同时排序，可以有效地利用多核处理器的并行处理能力。</span></li>
   <li fid="ud2193873" data-lake-id="u3ce92d36" id="u3ce92d36"><strong><span data-lake-id="u7ca546d7" id="u7ca546d7" class="lake-fontsize-12" style="color: var(--tw-prose-bold)">减少处理时间</span></strong><span data-lake-id="uf0eab434" id="uf0eab434" class="lake-fontsize-12" style="color: rgb(55, 65, 81)">：对于大型数组，传统的递归快速排序可能会因递归调用和单线程执行而较慢。</span><strong><span data-lake-id="u5387a17f" id="u5387a17f" class="lake-fontsize-12" style="color: var(--tw-prose-code)">ForkJoinPool</span></strong><span data-lake-id="ubdca6bb0" id="ubdca6bb0" class="lake-fontsize-12" style="color: rgb(55, 65, 81)"> 提供的并行执行能够显著减少这种情况下的总体处理时间。</span></li>
   <li fid="ud2193873" data-lake-id="ue85842cd" id="ue85842cd"><strong><span data-lake-id="u29bd5ccc" id="u29bd5ccc" class="lake-fontsize-12" style="color: var(--tw-prose-bold)">可伸缩性</span></strong><span data-lake-id="u70c6efc6" id="u70c6efc6" class="lake-fontsize-12" style="color: rgb(55, 65, 81)">：</span><strong><span data-lake-id="u30cd0e2f" id="u30cd0e2f" class="lake-fontsize-12" style="color: var(--tw-prose-code)">ForkJoinPool</span></strong><span data-lake-id="ufe778141" id="ufe778141" class="lake-fontsize-12" style="color: rgb(55, 65, 81)"> 能够根据系统的可用资源（如处理器核心数）动态调整并发级别。这意味着它可以在不同的硬件配置上提供良好的性能，特别是在多核处理器上。</span></li>
  </ol>
  <p data-lake-id="u12938c9d" id="u12938c9d"><br></p>
  <p data-lake-id="uc3c25c31" id="uc3c25c31"><span data-lake-id="u060238c8" id="u060238c8">下面是一个使用 ForkJoinPool 实现快排的代码：</span></p>
  <p data-lake-id="uaf215c23" id="uaf215c23"><span data-lake-id="ud706d221" id="ud706d221">​</span><br></p>
  <pre lang="java"><code>
import java.util.concurrent.RecursiveAction;
import java.util.concurrent.ForkJoinPool;

public class ParallelQuickSort extends RecursiveAction {
    private int[] array;
    private int left;
    private int right;

    public ParallelQuickSort(int[] array, int left, int right) {
        this.array = array;
        this.left = left;
        this.right = right;
    }

    private int partition(int left, int right) {
        int pivot = array[right];
        int i = left - 1;
        for (int j = left; j &lt; right; j++) {
            if (array[j] &lt;= pivot) {
                i++;
                // Swap array[i] and array[j]
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        // Swap array[i+1] and array[right] (or pivot)
        int temp = array[i + 1];
        array[i + 1] = array[right];
        array[right] = temp;
        return i + 1;
    }

    @Override
    protected void compute() {
        if (left &lt; right) {
            int partitionIndex = partition(left, right);

            // Parallelize the two subtasks
            ParallelQuickSort leftTask = new ParallelQuickSort(array, left, partitionIndex - 1);
            ParallelQuickSort rightTask = new ParallelQuickSort(array, partitionIndex + 1, right);

            leftTask.fork();
            rightTask.fork();
            
            leftTask.join();
            rightTask.join();
        }
    }

    public static void parallelQuickSort(int[] array) {
        ForkJoinPool pool = new ForkJoinPool();
        pool.invoke(new ParallelQuickSort(array, 0, array.length - 1));
    }

    public static void main(String[] args) {
        int[] array = { 12, 35, 87, 26, 9, 28, 7 };
        parallelQuickSort(array);
        for (int i : array) {
            System.out.print(i + " ");
        }
    }
}

</code></pre>
  <p data-lake-id="u81d5fd7e" id="u81d5fd7e"><span data-lake-id="u6b61184b" id="u6b61184b">​</span><br></p>
  <p data-lake-id="ub22b42e2" id="ub22b42e2"><br></p>
  <p data-lake-id="ue0f7febe" id="ue0f7febe"><br></p>
  <p data-lake-id="ub8b37740" id="ub8b37740"><span data-lake-id="u5cef962f" id="u5cef962f">ParallelQuickSort 类继承自 RecursiveAction。在这个类中，compute 方法实现了快速排序的逻辑，包括分区（partition 方法）和递归调用。对于每个递归调用，它创建了一个新的 ParallelQuickSort 实例，并通过 fork 方法将其提交给 ForkJoinPool 以异步执行。</span></p>
  <p data-lake-id="u02d4b850" id="u02d4b850"><br></p>
  <blockquote data-lake-id="u49d5c197" id="u49d5c197">
   <p data-lake-id="u142c1433" id="u142c1433"><span data-lake-id="u189c5ba5" id="u189c5ba5">RecursiveAction 是用于创建没有返回值的递归任务的基类。</span></p>
  </blockquote>
  <p data-lake-id="u3d5318f0" id="u3d5318f0"><br></p>
  <p data-lake-id="uc3fc3dc2" id="uc3fc3dc2"><span data-lake-id="u8d7cd19d" id="u8d7cd19d">这个实现通过将快速排序的左右部分分解为独立的任务来实现并行化。在大数据集上，这可以有效利用多核处理器，从而加快排序过程。然而，对于小数组，传统的快速排序可能更高效，因为并行化引入的额外开销可能不值得。</span></p>
 </body>
</html>